// 一条包含字母 A-Z 的消息通过以下方式进行了编码：

// 'A' -> 1
// 'B' -> 2
// ...
// 'Z' -> 26
// 给定一个只包含数字的非空字符串，请计算解码方法的总数。

// 示例 1:

// 输入: "12"
// 输出: 2
// 解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。
// 示例 2:

// 输入: "226"
// 输出: 3
// 解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

#include <string>
#include <vector>

using std::vector;
using std::string;

class Solution1 {
public:
    int numDecodings(string s) {
        if (s.empty() || s[0] == '0') return 0;
        int n = s.size();
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        for (int i{1}; i < n + 1; ++i) {
            dp[i] = (s[i-1] == '0') ? 0 : dp[i - 1];
            if (i > 1 && (s[i - 2] == '1' || (s[i-2] == '2' && s[i-1] <= '6'))) {
                dp[i] += dp[i-2];
            }
        }
        return dp[n];
    }
};

class Solution {
public:
    int numDecodings(string s) {
        if (s.empty() || s[0] == '0') return 0;
        int a{1}; // s[i-1]
        int b{1}; // s[i-2]
        int n{s.size()};
        for (int i{1}; i < n; ++i) {
            if (s[i] == '0') a = 0;
            if (s[i-1] == '1' || (s[i-1] == '2' && s[i] <= '6')) {
                a += b;
                b = a - b; // b赋值为之前的a
            } else {
                b = a;
            }
        }
        return a;
    }
};

// dynamic programming
class Solution {
public:
    int numDecodings(string s) {
        if (s.empty() || s[0] = '0') {
            return 0;
        }
        int n = s.size();
        vector<int> dp(n + 1, 1);
        for (int i{1}; i <= n; ++i) {
            dp[i] = s[i - 1] == '0' ? 0 : dp[i - 1];
            if (i > 1 && (s[i-2] == '1' || (s[i-2] == '2' && s[i-1] <= '6'))) {
                dp[i] += dp[i-2];
            }
        }
        return dp[n];
    }
};